/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 076. 数组中的第 k 大的数字
 * @author: WXY
 * @create: 2023-01-12 17:36
 * @Version 1.0
 **/
public class offer_twentysix1_Solution {
    static class Solution {
        public static int findKthLargest(int[] nums, int k) {
            MyMinHeap heap = new MyMinHeap(k);
            int i = 0;
            for (; i < k; i++) {
                heap.push(nums[i]);
            }
            for (int j = i; j < nums.length; j++) {
                heap.push(nums[j]);
                heap.pop();
            }
            return heap.peek();
        }

        public static class MyMinHeap {
            private final int limit;
            private int[] heap;
            private int heapSize;

            public MyMinHeap(int limit) {
                heap = new int[limit];
                this.limit = limit;
                this.heapSize = 0;
            }

            public boolean isEmpty() {
                return heapSize == 0;
            }

            public int length() {
                return heapSize;
            }

            public boolean isFull() {
                return heapSize == limit;
            }

            public void push(int value) {
                if (heapSize == limit) {
                    return;
                }
                heap[heapSize] = value;
                heapInsert(heap, heapSize++);
            }

            public int pop() {
                int ans = heap[0];
                swap(heap, 0, --heapSize);
                heapify(heap, 0, heapSize);
                return ans;
            }

            public int peek() {
                return heap[0];
            }

            private void heapify(int[] arr, int index, int heapSize) {
                int left = index * 2 + 1;
                while (left < heapSize) {
                    int small = left + 1 < heapSize && arr[left + 1] < arr[left] ? left + 1 : left;
                    small = arr[small] < arr[index] ? small : index;
                    if (small == index) break;
                    swap(arr, small, index);
                    index = small;
                    left = left * 2 + 1;
                }
            }

            private void heapInsert(int[] arr, int index) {
                while (arr[index] < arr[(index - 1) / 2]) {
                    swap(arr, index, (index - 1) / 2);
                    index = (index - 1) / 2;
                }
            }

            private void swap(int[] heap, int i, int j) {
                int tmp = heap[i];
                heap[i] = heap[j];
                heap[j] = tmp;
            }

        }
    }
}
